package com.jianZhiOffer;

import java.util.ArrayList;
import java.util.List;

public class Solution17 {
    int[] res;
    char[] chars = new char[]{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    List<String> list = new ArrayList<>();

    public int[] printNumbers(int n) {
        if (n == 1) return new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        int len = (int) (Math.pow(10, n) - 1);
        res = new int[len];
        backtracking(n);
        for (int i = 0; i < len; i++) {
            res[i] = Integer.parseInt(list.get(i));
        }
        return res;
    }

    StringBuffer sb = new StringBuffer();

    public void backtracking(int n) {
        if (sb.length() == n) {
            String tmp = sb.toString();
            int i = 0;
            while (i < tmp.length() && tmp.charAt(i) == '0') i++;
            if (i < tmp.length()) list.add(tmp.substring(i));
            return;
        }
        for (int i = 0; i < 10; i++) {
            sb.append(chars[i]);
            backtracking(n);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
